

#  518.零钱兑换II

def change(amount, coins):
    dp = [[None] * (amount + 1) for _ in range(len(coins)+1)]
    for i in range(0, len(coins)+1):
        dp[i][0] = 1
    for i in range(0, amount+1):
        dp[0][i] = 0
    for i in range(1, len(coins)+1):
        for j in range(1, amount + 1):
            if j < coins[i-1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]]
    return dp[len(coins)][amount]


if __name__ == "__main__":
    amount = 5
    coins = [1,2,5]
    print(change(amount,coins))